Cryptographic applications of capacity theory: On the optimality of Coppersmith's method for univariate polynomials

摘要

We draw a new connection between Coppersmith's method for finding smallsolutions to polynomial congruences modulo integers and the capacity theory ofadelic subsets of algebraic curves. Coppersmith's method uses lattice basisreduction to construct an auxiliary polynomial that vanishes at the desiredsolutions. Capacity theory provides a toolkit for proving when polynomials withcertain boundedness properties do or do not exist. Using capacity theory, weprove that Coppersmith's bound for univariate polynomials is optimal in thesense that there are \emph{no} auxiliary polynomials of the type he used thatwould allow finding roots of size $N^{1/d+\epsilon}$ for monic degree-$d$polynomials modulo $N$. Our results rule out the existence of polynomials ofany degree and do not rely on lattice algorithms, thus eliminating thepossibility of even superpolynomial-time improvements to Coppersmith's bound.We extend this result to constructions of auxiliary polynomials using binomialpolynomials, and rule out the existence of any auxiliary polynomial of thisform that would find solutions of size $N^{1/d+\epsilon}$ unless $N$ has a verysmall prime factor.